1. Field of the Invention
The present invention relates in general to the field of information processing, and more specifically to a system and method for product configuration using efficient product representation and configuration logic processing procedures.
2. Description of the Related Art
A configurator is a software tool used to assist customers and sales persons in finding and ordering valid configurations of complex products. A configurator can also be used for other purposes, such as for correctly specifying products during manufacturing. Such products may have many selectable features and options subject to compatibility or other configuration constraints. The configurator is given a configuration model (sometimes called a knowledge base), which identifies the set of features defining the configuration space, and the set of combinations of features that correspond to valid configurations. Typically the set of valid configurations is not described extensionally. Rather, the configuration model uses a special-purpose declarative language with primitives chosen for their ability to express configuration logic concisely and maintainably.
Given a configuration model, the configurator interactively assists users in finding valid configurations that meet their needs. More specifically, the user interacts with the configurator, selecting desired product features one by one. After each new choice the configurator's core task is generally to find:                All features that are incompatible with the user's selections. A given feature is incompatible with the user's selections if there exists no valid configuration that contains both the user's selections and the given feature.        All features that are required by the user's selections. A given feature is required by the user's selections if every valid configuration that contains the user selections also contains the given feature.        
By providing feedback to the user showing which features are incompatible with, or required by, previous selections, the configurator makes it possible for the user find valid configurations without having to backtrack or search.
Note that the configurator typically performs other tasks as well. For example, it may generate explanations of how it reached its conclusions, it may determine which selections need to be retracted in order to select a feature that is currently excluded, and it may search for optimal or default configurations consistent with some partial set of user selections. Nevertheless, the task above remains the core task of the configurator because it typically plays a key part in algorithms for implementing other tasks.
The core configuration task we have described above is essentially the task of consequence finding. A natural way to approach it is to translate the configuration model into an expression of propositional logic and then treat the problem as one of propositional entailment:                Let M be the clausal database obtained by translating the configuration model into an expression of propositional logic in conjunctive normal form (CNF), i.e. a conjunction of clauses, of which each is a disjunction of literals.        Let U be a set of unit clauses representing user selections. (a unit clause is a clause containing a single literal).        The core configuration task is then to find every unit clause, C, where MU |=C, wherein “|=” is the symbol for entailment.        
One way to find all entailed unit clauses is to use a resolution-based consequence-finding algorithm such as Tison's prime implicates algorithm. Recall that resolution is an inference procedure whereby two parent clauses, C1 and C2, containing complementary literals, a and a, may be combined to produce a resolvent clause, R, containing the union of the literals of the parent clauses minus the complementary literals resolved upon. That is,                     C1        =                  {                      a            ,                          b              1                        ,            …            ⁢                                                  ,                          b              n                                }                                        C2        =                  {                                                  ⁢              a                        ,                          c              1                        ,            …            ⁢                                                  ,                          c              n                                }                                        R        =                  {                                    b              1                        ,            …            ⁢                                                  ,                          b              n                        ,                          c              1                        ,            …            ⁢                                                  ,                          c              n                                }                    General resolution is both sound and complete. Unfortunately, because a resolvent can include more literals than either of its parents, and thus may not subsume either parent, the number of clauses in the database can grow exponentially. Indeed, consequence finding with general resolution is NP-hard, and algorithms based on general resolution are not normally suitable for interactive systems where responsiveness is a key requirement.
The usual compromise is to use unit resolution, an incomplete inference procedure that may not find all entailed conclusions, but that is guaranteed to run in time linear in the number of literals in the database. Unit resolution is a restricted form of resolution that considers only resolutions where one of the parent clauses is a unit clause. For example:                {a, b1, . . . , bn}        {a}        ---------------        {b1, . . . , bn}        
Unit resolutions always produce resolvents that subsume their non-unit parents, thereby reducing the number of literals in the database by one. This being the case, the maximum number of unit resolutions that can ever be performed is equal to the number of literals in the database, and the cost of unit resolution is linear in the database size. This linear bound on the cost of unit resolution is an attractive characteristic and is generally worth the loss of completeness, especially since there are a number of techniques that can be used to compile a model into a form where the incompleteness disappears.
Translation of the configuration model into CNF and application of unit resolution would therefore seem to be a reasonable approach for solving the core configuration task.
Unfortunately, a significant practical problem arises when this process is applied to real configuration models. Recall that configuration models are typically written in special languages with primitives designed for expressing configuration logic concisely and maintainably. These configuration primitives can be translated into propositional logic, but conciseness of representation is usually lost along the way. In practice, these translations can lead to exponential growth in the size of the model's representation. In such cases, unit resolution's promise of linear performance becomes an empty one. Though the cost of inference remains linear with respect to the size of the translated model, it may be exponential with respect to the size of the original model.
As an example, consider the following case of ‘exclusive choices’.
A common constraint in configuration modeling is “you must choose exactly one member of this set”, or more generally, “you must choose at least A and at most B members of this set”, where A and B are nonnegative integers, and B≧A. This sort of (A,B) choice has no concise representation in propositional logic.
For example, suppose a model includes five colors represented by the variables a, b, c, d, and e, as well as the constraint “you must choose exactly one color”. This constraint can be split into two separate constraints: (1) “you must choose at least 1 color” and (2) “you must choose at most 1 color”.
Constraint (1) can be written simply as a single conventional clause:                {a, b, c, d, e}        
However, constraint (2) must be represented by a series of conventional clauses, one for each pair of colors that can't be selected together:                {a, b}        {a, c}        {a, d}        {a, e}        {b, c}        {b, d}        {b, e}        {c, d}        {c, e}        {d, e}.        
In general, if N is the number of features in the set and A is the minimum that must be chosen and B is the maximum that must be chosen, then representing the choice in conventional propositional logic requires . . .   (                                   N                                                  N            -            A            +            1                                )                  clauses expressing the minimum constraint, and . . .   (                                   N                                                  B            +            1                                )          clauses expressing the maximum constraint, where expressions of the form . . .          (                            N                                      M                      )          represent “N choose M”, i.e., the number of ways to choose M elements from a set of N. Mathematically, “N choose M” is defined as N!/(M!(N−M)!), a function that can grow exponentially with N.        
As Table 1 illustrates, if the minimum, A, and maximum, B, are both one, then the number of clauses in a CNF representation of the choice grows quadratically with respect to N. With arbitrary minimums and maximums the number of clauses grows much faster, with the worst case being a minimum or maximum equals to N/2.
TABLE 1A - MinimumB - MaximumMinimumMaximumChoicesNumberNumberClausesClauses5111101011145201111902021820202051548454845201010167960167960
The growth encountered when translating the “exclusive choices” configuration constraint into propositional logic illustrates that a guarantee of linear performance with respect to the size of a model in CNF is far from a guarantee of linear performance with respect to its size in its original form (using the min/max choice primitive). From Table 1 we see that a rule stated as simply as “you must choose exactly ten of these twenty things” would have a CNF representation with 335,920 clauses containing a total of 3,695,120 literals.
As another example, consider the following case of ‘resource constraints’.
Another common configuration primitive is the resource constraint. Certain components are identified as providers of a given resource and other components are identified as consumers of the resource. The resource constraint states that the amount of resource provided by selected providers must equal or exceed the amount of resource consumed by selected consumers.
For example, suppose we have a power resource and the following providers and consumers as depicted in Table 2:
TABLE 2Power unitsPower unitsProviderprovidedConsumerconsumedPowerSupply1100HardDrive150PowerSupply2200HardDrive2150HardDrive3150
Given these resources, Table 3 is an example of the consequences of selecting different combinations of hard drives, where ‘user-selected’ indicates a user selection, ‘INCLUDED’ indicates a feature required by the user selections, ‘EXCLUDED’ indicates a feature incompatible with the user selections, and ‘--’, indicate a feature that may validly be selected or left out.
TABLE 3Power-Power-HardDrive1HardDrive2HardDrive3Supply1Supply2user-selected—————user-selected——INCLUDED——User-selected—INCLUDEDuser-selecteduser-selectedEXCLUDED—INCLUDEDuser-selectedEXCLUDEDUser-selected—INCLUDEDEXCLUDEDuser-selectedUser-selectedINCLUDEDINCLUDED
Table 4 is an example of the consequences of user-excluding power supplies in conjunction with selecting hard drives (‘user-excluded’ means that the user has indicated that the given feature must not be included in the configuration).
TABLE 4Power-Power-HardDrive1HardDrive2HardDrive3Supply1Supply2—EXCLUDEDEXCLUDED—Excluded—user-selectedEXCLUDEDuser-INCLUDEDexcluded
Because resource-oriented logic is fundamentally about summing and comparing quantities, it is neither convenient nor efficient to represent prepositionally. Representing resource-oriented logic prepositionally involves finding every possible combination of selected resource consumers and excluded resource providers that violates the resource constraint and writing a rule to exclude that combination. If P and C are the numbers of providers and consumers respectively, then there are 2(P+C) possible combinations of selected consumers and excluded providers. Of these a subset may violate the constraint, and of those a subset may be eliminated via subsumption. Nevertheless, the sets of clauses representing the combinations are exponential in size and the representational growth we encounter may be dramatic.